UVa/11466 - Largest prime divisor/11466.cpp

   1 #include <iostream>
   2 #include <map>
   3 #include <cassert>
   4 #include <algorithm>
   5 #include <cmath>
   6
   7 using namespace std;
   8
   9 typedef unsigned long long ull;
  10 typedef long long ll;
  11
  12 map<ull, long long> cache;
  13
  14 void f(ull x)
  15 {
  16   ull i;                 /* counter */
  17   ull c;                 /* remaining product to factor */
  18   ll r = cache[x];
  19   if (r == 0){
  20     c = x;
  21     while ((c % 2) == 0) {
  22       //printf("2\n");
  23       c = c / 2;
  24       r = 2;
  25     }
  26     i = 3;
  27     ull raiz = sqrt(c)+1;
  28     while (i <= raiz) {
  29       if ((c % i) == 0) {
  30         //printf("i: %lld\n", i);
  31         c = c / i;
  32         raiz = (sqrt(c)+1);
  33         r = i;
  34       }
  35       else
  36         i = i + 2;
  37     }
  38     if (c > r){
  39       r =  c;
  40       //printf("c: %lld\n", c);
  41     }
  42     //printf("c quedo en: %lld\n", c);
  43     //printf("r quedo en: %lld\n", r);
  44
  45     c = r;
  46     while (c <= x){
  47       if (c == x){
  48         r = -1;
  49         break;
  50       }
  51       c *= r;
  52     }
  53     cache[x] = r;
  54   }
  55   printf("%lld\n", r);
  56   //assert(r < x);
  57 }
  58
  59
  60 int main(){
  61   long long n;
  62   while (scanf("%lld", &n) == 1 && n){
  63     if (n < 0) n *= -1;
  64     //assert(n > 0);
  65     f(n);
  66   }
  67   return 0;
  68 }